#pragma warning disable IDE0073 // The file header does not match the required text
//----------------------------------------------------------------
// Copyright (c) Microsoft Corporation.  All rights reserved.
//----------------------------------------------------------------

namespace System;

using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Collections.Specialized;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Runtime;
using System.Runtime.CompilerServices;
using System.ServiceModel;

// this class is thread-safe
[TypeForwardedFrom("System.ServiceModel.Web, Version=3.5.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35")]
public class UriTemplateTable {
	Uri baseAddress;
	string basePath;
	Dictionary<string, FastPathInfo> fastPathTable; // key is uri.PathAndQuery, fastPathTable may be null
	bool noTemplateHasQueryPart;
	int numSegmentsInBaseAddress;
	Uri originalUncanonicalizedBaseAddress;
	UriTemplateTrieNode rootNode;
	UriTemplatesCollection templates;
	object thisLock;
	bool addTrailingSlashToBaseAddress;

	public UriTemplateTable()
		: this(null, null, true) {
	}
	public UriTemplateTable(IEnumerable<KeyValuePair<UriTemplate, object>> keyValuePairs)
		: this(null, keyValuePairs, true) {
	}
	public UriTemplateTable(Uri baseAddress)
		: this(baseAddress, null, true) {
	}

	internal UriTemplateTable(Uri baseAddress, bool addTrailingSlashToBaseAddress)
		: this(baseAddress, null, addTrailingSlashToBaseAddress) {
	}

	public UriTemplateTable(Uri baseAddress, IEnumerable<KeyValuePair<UriTemplate, object>> keyValuePairs)
		: this(baseAddress, keyValuePairs, true) {
	}

	internal UriTemplateTable(Uri baseAddress, IEnumerable<KeyValuePair<UriTemplate, object>> keyValuePairs, bool addTrailingSlashToBaseAddress) {
		if (baseAddress != null && !baseAddress.IsAbsoluteUri) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("baseAddress", SR.GetString(
				SR.UTTMustBeAbsolute));
		}

		this.addTrailingSlashToBaseAddress = addTrailingSlashToBaseAddress;
		this.originalUncanonicalizedBaseAddress = baseAddress;

		if (keyValuePairs != null) {
			this.templates = new UriTemplatesCollection(keyValuePairs);
		} else {
			this.templates = new UriTemplatesCollection();
		}

		this.thisLock = new object();
		this.baseAddress = baseAddress;
		NormalizeBaseAddress();
	}

	public Uri BaseAddress {
		get {
			return this.baseAddress;
		}
		set {
			if (value == null) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("value");
			}
			lock (this.thisLock) {
				if (this.IsReadOnly) {
					throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
						SR.GetString(SR.UTTCannotChangeBaseAddress)));
				} else {
					if (!value.IsAbsoluteUri) {
						throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("value", SR.GetString(
							SR.UTTBaseAddressMustBeAbsolute));
					} else {
						this.originalUncanonicalizedBaseAddress = value;
						this.baseAddress = value;
						NormalizeBaseAddress();
					}
				}
			}
		}
	}

	public Uri OriginalBaseAddress {
		get {
			return this.originalUncanonicalizedBaseAddress;
		}
	}

	public bool IsReadOnly {
		get {
			return this.templates.IsFrozen;
		}
	}
	public IList<KeyValuePair<UriTemplate, object>> KeyValuePairs {
		get {
			return this.templates;
		}
	}

	public void MakeReadOnly(bool allowDuplicateEquivalentUriTemplates) {
		// idempotent
		lock (this.thisLock) {
			if (!this.IsReadOnly) {
				this.templates.Freeze();
				Validate(allowDuplicateEquivalentUriTemplates);
				ConstructFastPathTable();
			}
		}
	}
	public Collection<UriTemplateMatch> Match(Uri uri) {
		if (uri == null) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("uri");
		}
		if (!uri.IsAbsoluteUri) {
			return None();
		}

		this.MakeReadOnly(true);

		// Matching path :
		Collection<String> relativeSegments;
		IList<UriTemplateTableMatchCandidate> candidates;
		if (!FastComputeRelativeSegmentsAndLookup(uri, out relativeSegments, out candidates)) {
			return None();
		}
		// Matching query :
		NameValueCollection queryParameters = null;
		if (!this.noTemplateHasQueryPart && AtLeastOneCandidateHasQueryPart(candidates)) {
			Collection<UriTemplateTableMatchCandidate> nextCandidates = new Collection<UriTemplateTableMatchCandidate>();
			Fx.Assert(nextCandidates.Count == 0, "nextCandidates should be empty");

			// then deal with query
			queryParameters = UriTemplateHelpers.ParseQueryString(uri.Query);
			bool mustBeEspeciallyInteresting = NoCandidateHasQueryLiteralRequirementsAndThereIsAnEmptyFallback(candidates);
			for (int i = 0; i < candidates.Count; i++) {
				if (UriTemplateHelpers.CanMatchQueryInterestingly(candidates[i].Template, queryParameters, mustBeEspeciallyInteresting)) {
					nextCandidates.Add(candidates[i]);
				}
			}
			if (nextCandidates.Count > 1) {
				Fx.Assert(AllEquivalent(nextCandidates, 0, nextCandidates.Count), "demux algorithm problem, multiple non-equivalent matches");
			}

			if (nextCandidates.Count == 0) {
				for (int i = 0; i < candidates.Count; i++) {
					if (UriTemplateHelpers.CanMatchQueryTrivially(candidates[i].Template)) {
						nextCandidates.Add(candidates[i]);
					}
				}
			}
			if (nextCandidates.Count == 0) {
				return None();
			}
			if (nextCandidates.Count > 1) {
				Fx.Assert(AllEquivalent(nextCandidates, 0, nextCandidates.Count), "demux algorithm problem, multiple non-equivalent matches");
			}

			candidates = nextCandidates;
		}
		// Verifying that we have not broken the allowDuplicates settings because of terminal defaults
		//  This situation can be caused when we are hosting ".../" and ".../{foo=xyz}" in the same
		//  table. They are not equivalent; yet they reside together in the same path partially-equivalent
		//  set. If we hit a uri that ends up in that particular end-of-path set, we want to provide the
		//  user only the 'best' match and not both; thus preventing inconsistancy between the MakeReadonly
		//  settings and the matching results. We will assume that the 'best' matches will be the ones with
		//  the smallest number of segments - this will prefer ".../" over ".../{x=1}[/...]".
		if (NotAllCandidatesArePathFullyEquivalent(candidates)) {
			Collection<UriTemplateTableMatchCandidate> nextCandidates = new Collection<UriTemplateTableMatchCandidate>();
			int minSegmentsCount = -1;
			for (int i = 0; i < candidates.Count; i++) {
				UriTemplateTableMatchCandidate candidate = candidates[i];
				if (minSegmentsCount == -1) {
					minSegmentsCount = candidate.Template.segments.Count;
					nextCandidates.Add(candidate);
				} else if (candidate.Template.segments.Count < minSegmentsCount) {
					minSegmentsCount = candidate.Template.segments.Count;
					nextCandidates.Clear();
					nextCandidates.Add(candidate);
				} else if (candidate.Template.segments.Count == minSegmentsCount) {
					nextCandidates.Add(candidate);
				}
			}
			Fx.Assert(minSegmentsCount != -1, "At least the first entry in the list should be kept");
			Fx.Assert(nextCandidates.Count >= 1, "At least the first entry in the list should be kept");
			Fx.Assert(nextCandidates[0].Template.segments.Count == minSegmentsCount, "Trivial");
			candidates = nextCandidates;
		}

		// Building the actual result
		Collection<UriTemplateMatch> actualResults = new Collection<UriTemplateMatch>();
		for (int i = 0; i < candidates.Count; i++) {
			UriTemplateTableMatchCandidate candidate = candidates[i];
			UriTemplateMatch match = candidate.Template.CreateUriTemplateMatch(this.originalUncanonicalizedBaseAddress,
				uri, candidate.Data, candidate.SegmentsCount, relativeSegments, queryParameters);
			actualResults.Add(match);
		}
		return actualResults;
	}
	public UriTemplateMatch MatchSingle(Uri uri) {
		Collection<UriTemplateMatch> c = this.Match(uri);
		if (c.Count == 0) {
			return null;
		}
		if (c.Count == 1) {
			return c[0];
		}
		throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new UriTemplateMatchException(SR.GetString(
			SR.UTTMultipleMatches)));
	}

	[SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode", Justification = "This method is called within a Debug assert")]
	static bool AllEquivalent(IList<UriTemplateTableMatchCandidate> list, int a, int b) {
		for (int i = a; i < b - 1; ++i) {
			if (!list[i].Template.IsPathPartiallyEquivalentAt(list[i + 1].Template, list[i].SegmentsCount)) {
				return false;
			}
			if (!list[i].Template.IsQueryEquivalent(list[i + 1].Template)) {
				return false;
			}
		}
		return true;
	}

	static bool AtLeastOneCandidateHasQueryPart(IList<UriTemplateTableMatchCandidate> candidates) {
		for (int i = 0; i < candidates.Count; i++) {
			if (!UriTemplateHelpers.CanMatchQueryTrivially(candidates[i].Template)) {
				return true;
			}
		}
		return false;
	}
	static bool NoCandidateHasQueryLiteralRequirementsAndThereIsAnEmptyFallback(
		IList<UriTemplateTableMatchCandidate> candidates) {
		bool thereIsAmEmptyFallback = false;
		for (int i = 0; i < candidates.Count; i++) {
			if (UriTemplateHelpers.HasQueryLiteralRequirements(candidates[i].Template)) {
				return false;
			}
			if (candidates[i].Template.queries.Count == 0) {
				thereIsAmEmptyFallback = true;
			}
		}
		return thereIsAmEmptyFallback;
	}

	static Collection<UriTemplateMatch> None() {
		return new Collection<UriTemplateMatch>();
	}
	static bool NotAllCandidatesArePathFullyEquivalent(IList<UriTemplateTableMatchCandidate> candidates) {
		if (candidates.Count <= 1) {
			return false;
		}

		int segmentsCount = -1;
		for (int i = 0; i < candidates.Count; i++) {
			if (segmentsCount == -1) {
				segmentsCount = candidates[i].Template.segments.Count;
			} else if (segmentsCount != candidates[i].Template.segments.Count) {
				return true;
			}
		}
		return false;
	}

	bool ComputeRelativeSegmentsAndLookup(Uri uri,
		ICollection<string> relativePathSegments, // add to this
		ICollection<UriTemplateTableMatchCandidate> candidates) // matched candidates
	{
		string[] uriSegments = uri.Segments;
		int numRelativeSegments = uriSegments.Length - this.numSegmentsInBaseAddress;
		Fx.Assert(numRelativeSegments >= 0, "bad num segments");
		UriTemplateLiteralPathSegment[] uSegments = new UriTemplateLiteralPathSegment[numRelativeSegments];
		for (int i = 0; i < numRelativeSegments; ++i) {
			string seg = uriSegments[i + this.numSegmentsInBaseAddress];
			// compute representation for matching
			UriTemplateLiteralPathSegment lps = UriTemplateLiteralPathSegment.CreateFromWireData(seg);
			uSegments[i] = lps;
			// compute representation to project out into results
			string relPathSeg = Uri.UnescapeDataString(seg);
			if (lps.EndsWithSlash) {
				Fx.Assert(relPathSeg.EndsWith("/", StringComparison.Ordinal), "problem with relative path segment");
				relPathSeg = relPathSeg.Substring(0, relPathSeg.Length - 1); // trim slash
			}
			relativePathSegments.Add(relPathSeg);
		}
		return rootNode.Match(uSegments, candidates);
	}
	void ConstructFastPathTable() {
		this.noTemplateHasQueryPart = true;
		foreach (KeyValuePair<UriTemplate, object> kvp in this.templates) {
			UriTemplate ut = kvp.Key;
			if (!UriTemplateHelpers.CanMatchQueryTrivially(ut)) {
				this.noTemplateHasQueryPart = false;
			}
			if (ut.HasNoVariables && !ut.HasWildcard) {
				// eligible for fast path
				if (this.fastPathTable == null) {
					this.fastPathTable = new Dictionary<string, FastPathInfo>();
				}
				Uri uri = ut.BindByPosition(this.originalUncanonicalizedBaseAddress);
				string uriPath = UriTemplateHelpers.GetUriPath(uri);
				if (this.fastPathTable.ContainsKey(uriPath)) {
					// nothing to do, we've already seen it
				} else {
					FastPathInfo fpInfo = new FastPathInfo();
					if (ComputeRelativeSegmentsAndLookup(uri, fpInfo.RelativePathSegments,
						fpInfo.Candidates)) {
						fpInfo.Freeze();
						this.fastPathTable.Add(uriPath, fpInfo);
					}
				}
			}
		}
	}
	// this method checks the literal cache for a match if none, goes through the slower path of cracking the segments
	bool FastComputeRelativeSegmentsAndLookup(Uri uri, out Collection<string> relativePathSegments,
		out IList<UriTemplateTableMatchCandidate> candidates) {
		// Consider fast-path and lookup
		// return false if not under base uri
		string uriPath = UriTemplateHelpers.GetUriPath(uri);
		FastPathInfo fpInfo = null;
		if ((this.fastPathTable != null) && this.fastPathTable.TryGetValue(uriPath, out fpInfo)) {
			relativePathSegments = fpInfo.RelativePathSegments;
			candidates = fpInfo.Candidates;
			VerifyThatFastPathAndSlowPathHaveSameResults(uri, relativePathSegments, candidates);
			return true;
		} else {
			relativePathSegments = new Collection<string>();
			candidates = new Collection<UriTemplateTableMatchCandidate>();
			return SlowComputeRelativeSegmentsAndLookup(uri, uriPath, relativePathSegments, candidates);
		}
	}

	void NormalizeBaseAddress() {
		if (this.baseAddress != null) {
			// ensure trailing slash on baseAddress, so that IsBaseOf will work later
			UriBuilder ub = new UriBuilder(this.baseAddress);
			if (this.addTrailingSlashToBaseAddress && !ub.Path.EndsWith("/", StringComparison.Ordinal)) {
				ub.Path = ub.Path + "/";
			}
			ub.Host = "localhost"; // always normalize to localhost
			ub.Port = -1;
			ub.UserName = null;
			ub.Password = null;
			ub.Path = ub.Path.ToUpperInvariant();
			ub.Scheme = Uri.UriSchemeHttp;
			this.baseAddress = ub.Uri;
			basePath = UriTemplateHelpers.GetUriPath(this.baseAddress);
		}
	}
	bool SlowComputeRelativeSegmentsAndLookup(Uri uri, string uriPath, Collection<string> relativePathSegments,
		ICollection<UriTemplateTableMatchCandidate> candidates) {
		// ensure 'under' the base address
		if (uriPath.Length < basePath.Length) {
			return false;
		}

		if (!uriPath.StartsWith(basePath, StringComparison.OrdinalIgnoreCase)) {
			return false;
		} else {
			// uriPath StartsWith basePath, but this check is not enough - basePath 'service1' should not match with uriPath 'service123'
			// make sure that after the match the next character is /, this is to avoid a uriPath of the form /service12/ matching with a basepath of the form /service1
			if (uriPath.Length > basePath.Length && !basePath.EndsWith("/", StringComparison.Ordinal) && uriPath[basePath.Length] != '/') {
				return false;
			}
		}

		return ComputeRelativeSegmentsAndLookup(uri, relativePathSegments, candidates);
	}

	void Validate(bool allowDuplicateEquivalentUriTemplates) {
		if (this.baseAddress == null) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(
				SR.UTTBaseAddressNotSet)));
		}
		this.numSegmentsInBaseAddress = this.baseAddress.Segments.Length;
		if (this.templates.Count == 0) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(
				SR.UTTEmptyKeyValuePairs)));
		}
		// build the trie and
		// validate that forall Uri u, at most one UriTemplate is a best match for u
		rootNode = UriTemplateTrieNode.Make(this.templates, allowDuplicateEquivalentUriTemplates);
	}
	[Conditional("DEBUG")]
	void VerifyThatFastPathAndSlowPathHaveSameResults(Uri uri, Collection<string> fastPathRelativePathSegments,
		IList<UriTemplateTableMatchCandidate> fastPathCandidates) {
		Collection<string> slowPathRelativePathSegments = new Collection<string>();
		List<UriTemplateTableMatchCandidate> slowPathCandidates = new List<UriTemplateTableMatchCandidate>();
		if (!SlowComputeRelativeSegmentsAndLookup(uri, UriTemplateHelpers.GetUriPath(uri),
			slowPathRelativePathSegments, slowPathCandidates)) {
			Fx.Assert("fast path yielded a result but slow path yielded no result");
		}
		// compare results
		if (fastPathRelativePathSegments.Count != slowPathRelativePathSegments.Count) {
			Fx.Assert("fast path yielded different number of segments from slow path");
		}
		for (int i = 0; i < fastPathRelativePathSegments.Count; ++i) {
			if (fastPathRelativePathSegments[i] != slowPathRelativePathSegments[i]) {
				Fx.Assert("fast path yielded different segments from slow path");
			}
		}
		if (fastPathCandidates.Count != slowPathCandidates.Count) {
			Fx.Assert("fast path yielded different number of candidates from slow path");
		}
		for (int i = 0; i < fastPathCandidates.Count; i++) {
			if (!slowPathCandidates.Contains(fastPathCandidates[i])) {
				Fx.Assert("fast path yielded different candidates from slow path");
			}
		}
	}

	class FastPathInfo {
		FreezableCollection<UriTemplateTableMatchCandidate> candidates;
		FreezableCollection<string> relativePathSegments;

		public FastPathInfo() {
			this.relativePathSegments = new FreezableCollection<string>();
			this.candidates = new FreezableCollection<UriTemplateTableMatchCandidate>();
		}
		public Collection<UriTemplateTableMatchCandidate> Candidates {
			get {
				return this.candidates;
			}
		}

		public Collection<string> RelativePathSegments {
			get {
				return this.relativePathSegments;
			}
		}

		public void Freeze() {
			this.relativePathSegments.Freeze();
			this.candidates.Freeze();
		}
	}

	class UriTemplatesCollection : FreezableCollection<KeyValuePair<UriTemplate, object>> {
		public UriTemplatesCollection()
			: base() {
		}
		[SuppressMessage("Microsoft.Usage", "CA2214:DoNotCallOverridableMethodsInConstructors", Justification = "This is a private class; virtual methods cannot be overriden")]
		public UriTemplatesCollection(IEnumerable<KeyValuePair<UriTemplate, object>> keyValuePairs)
			: base() {
			foreach (KeyValuePair<UriTemplate, object> kvp in keyValuePairs) {
				ThrowIfInvalid(kvp.Key, "keyValuePairs");
				base.Add(kvp);
			}
		}

		protected override void InsertItem(int index, KeyValuePair<UriTemplate, object> item) {
			ThrowIfInvalid(item.Key, "item");
			base.InsertItem(index, item);
		}
		protected override void SetItem(int index, KeyValuePair<UriTemplate, object> item) {
			ThrowIfInvalid(item.Key, "item");
			base.SetItem(index, item);
		}

		static void ThrowIfInvalid(UriTemplate template, string argName) {
			if (template == null) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument(argName,
					SR.GetString(SR.UTTNullTemplateKey));
			}
			if (template.IgnoreTrailingSlash) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument(argName,
					SR.GetString(SR.UTTInvalidTemplateKey, template));
			}
		}
	}
}
